import random
import time

from sort.Sort import Sort


class QuickSort(Sort):
    def __init__(self):
        super().__init__()

    def sort(self, arr_list):
        """
        快速排序：
            基本思想：
              1. 将集合构建成一个双边集合（一边全部小于等于基数，一边全部大于基数）
              2. 如果子集合元素数大于2，将两个的子集合分别作为集合重复第1步
            注意要点：
              1. 中间可能由于重复数据出现死循环，即当从两边选取值交换时，如果两边值相等将出现循环
        :param arr_list: 原始无序集合
        :return: 有序集合
        """
        self.quick_sort(arr_list, 0, len(arr_list) - 1)
        return arr_list

    def quick_sort(self, arr_list, left, right):
        l = left
        r = right
        center = arr_list[(left + right) // 2]

        while True:
            while l < r and arr_list[l] < center:
                l += 1

            while l < r and arr_list[r] > center:
                r -= 1

            # 当两个指针相遇时，该位置的数为center
            if l == r:
                break

            # 两个元素互换，python中的特殊写法，类似java中的 swap三行
            arr_list[l], arr_list[r] = arr_list[r], arr_list[l]

            if arr_list[l] == arr_list[r]:
                # 放置由于重复数据导致的死循环，当出现这种情况时选择左指针右移一位
                l += 1

        #  如果子序列元素大于一个则递归处理
        if left < l - 1:
            self.quick_sort(arr_list, left, l - 1)
        if l + 1 < right:
            self.quick_sort(arr_list, l + 1, right)


if __name__ == '__main__':
    # arr = [2, 5, 3, 7, 1, 4, 6]
    arr = [2, 3, 1, 1, 2, 3, 2, 1, 3]
    # arr = [random.randint(0, 80000) * i for i in range(0, 80000)]
    print(arr)
    start_time = time.time()
    sort = QuickSort()
    sort_arr = sort.sort(arr)
    print(sort_arr)
    print()
    print("快速排序80000数据共计使用{}秒".format(str(int(time.time() - start_time))))
